'''
快速排序:是对冒泡排序的一种改进,思路是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
时间复杂度: 最坏:O(n²)
稳定性:不稳定
'''


def quick_sort(list, start, end):
    if start >= end:
        return
    low = start
    hight = end
    mid_value = list[low]
    while low < hight:
        while low < hight and list[hight] >= mid_value:
            hight -= 1
        list[low] = list[hight]  # 把右边小的值放到左边
        while low < hight and list[low] < mid_value:
            low += 1
        list[hight] = list[low]  # 把左边边大的值放到右边
    # low与hight相等时跳出循环
    list[low] = mid_value
    quick_sort(list, start, low - 1)
    quick_sort(list, hight + 1, end)


if __name__ == '__main__':
    li = [31, 65, 12, 98, 54, 21, 100, 4]
    quick_sort(li, 0, len(li) - 1)
    print(li)
